#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

// 事件结构体
struct Event {
    int time;  // 下一次到达站点的事件发生的时间
    int car_id; // 车辆的ID
    int from;  // 车辆当前所在的节点
    int to;    // 车辆即将到达的节点
    Event(int time, int id, int a, int b) : time(time), car_id(id), from(a), to(b) {}

    // 重载比较操作，使剩余等待时间越短越先出队
    bool operator<(const Event& next) const {
        return this->time > next.time;
    }
};

// Dijkstra算法，用于计算某一辆车的最短路径
vector<int> dijkstra(int N, int start, int end, const vector<vector<int>>& roadlength, const vector<vector<int>>& flow, const vector<vector<int>>& restrictions) {
    vector<int> distance(N, INT_MAX); // 存储从起点到各节点的最短距离
    vector<int> previous(N, -1);     // 存储前驱节点
    vector<bool> visited(N, false);  // 记录节点是否已被访问

    distance[start] = 0; // 起点到自身的距离为0

    for (int i = 0; i < N - 1; i++) {
        int min_distance = INT_MAX;
        int stop = start;

        // 找到未访问节点中距离最小的节点
        for (int j = 0; j < N; j++) {
            if (!visited[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                stop = j;
            }
        }

        visited[stop] = true; // 标记该节点为已访问

        // 更新相邻节点的距离
        for (int k = 0; k < N; k++) {
            if (!visited[k] && roadlength[stop][k] < INT_MAX && flow[stop][k] < restrictions[stop][k] && distance[stop] + roadlength[stop][k] < distance[k]) {
                distance[k] = distance[stop] + roadlength[stop][k];
                previous[k] = stop;
            }
        }
    }

    // 构建最短路径
    vector<int> path;
    int node = end;
    while (node != -1) {
        path.push_back(node);
        node = previous[node];
    }
    reverse(path.begin(), path.end()); // 反转路径，使其从起点到终点

    return path;
}

int main() {
    int N, M;
    cin >> N >> M;

    // 使用二维 vector 替代二级指针数组
    vector<vector<int>> roadlength(N, vector<int>(N, INT_MAX)); // 存储道路长度
    vector<vector<int>> restrictions(N, vector<int>(N));       // 存储道路的流量限制
    vector<vector<int>> cars(M, vector<int>(2));               // 存储每辆车的起点和终点

    // 读取道路长度
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> roadlength[i][j];
            if (roadlength[i][j] == 0 && i != j) {
                roadlength[i][j] = INT_MAX; // 如果道路长度为0，则距离为无穷大
            }
        }
    }

    // 读取道路的流量限制
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> restrictions[i][j];
        }
    }

    // 读取每辆车的起点和终点
    for (int i = 0; i < M; i++) {
        cin >> cars[i][0] >> cars[i][1];
        cars[i][0]--; // 将输入的起点和终点转换为从0开始的索引
        cars[i][1]--;
    }

    // 初始化流量矩阵
    vector<vector<int>> flow(N, vector<int>(N, 0)); // 初始化流量为0

    // 为每辆车找到初始路径，并设置事件
    priority_queue<Event> event_queue;
    vector<vector<int>> paths(M);      // 存储每辆车的路径
    vector<vector<int>> history(M);    // 存储每辆车的历史路径
    vector<int> car_arrival_time(M, -1); // 存储每辆车的到达时间，初始为-1

    for (int i = 0; i < M; i++) {
        paths[i] = dijkstra(N, cars[i][0], cars[i][1], roadlength, flow, restrictions);

        // 路径中必定至少有一个end，所以路径长度至少为1
        if (paths[i].size() == 1) {
            // 如果无法到达？所有路全都堵了
            if (paths[i][0] == cars[i][0]) { // 出发点就是终点
                car_arrival_time[i] = 0;
                history[i].push_back(cars[i][0]);
                history[i].push_back(cars[i][0]);
                continue;
            } else {
                history[i].push_back(cars[i][0]);
                event_queue.push(Event(1, i, cars[i][0], cars[i][0])); // 使其延长1s再运行
                continue;
            }
        }

        history[i].push_back(cars[i][0]);
        int u = paths[i][0];
        int v = paths[i][1];
        int time = roadlength[u][v];
        event_queue.push(Event(time, i, u, v)); // 将车辆移动事件加入队列
        flow[u][v]++; // 更新流量
        flow[v][u]++;

        // 从路径中移除起点，因为车辆已经从起点出发
        paths[i].erase(paths[i].begin());
    }

    while (!event_queue.empty()) {
        int current_time = event_queue.top().time;
        //cout << current_time << endl;

        vector<Event> current_events;
        // 处理所有到达下一站的车辆
        while (!event_queue.empty() && event_queue.top().time == current_time) {
            Event event = event_queue.top();
            current_events.push_back(event);
            event_queue.pop();
            if (event.from != event.to) { // 若相等则为在某一个路口堵车的车辆，因此不用继续加
                flow[event.from][event.to]--;
                flow[event.to][event.from]--;
                history[event.car_id].push_back(event.to); // 历史记录只保存已经到达的站点
            }
        }
        for (Event event : current_events) {
            if (event.to == cars[event.car_id][1]) { // 表示到达目的地
                car_arrival_time[event.car_id] = current_time;
            } else { // 重新规划路径
                vector<int> newpath = dijkstra(N, history[event.car_id].back(), cars[event.car_id][1], roadlength, flow, restrictions);
                if (newpath.size() == 1) {
                    // 如果无法到达？所有路全都堵了
                    event_queue.push(Event(current_time+1, event.car_id, event.from, event.to)); // 使其延长1s再运行
                    continue;
                } else { // 能够到达
                    paths[event.car_id] = newpath;
                    int u = newpath[0];
                    int v = newpath[1];
                    flow[u][v]++; // 更新流量
                    flow[v][u]++;
                    int travel_time = current_time + roadlength[u][v];
                    event_queue.push(Event(travel_time, event.car_id, u, v));
                }
            }
        }
    }

    // 输出每辆车的行驶路线
    for (int i = 0; i < M; i++) {
        if (history[i][0] != cars[i][0]) cout << cars[i][0] + 1 << " "; // 输出起点
        for (int node : history[i]) {
            cout << node + 1; // 输出路径中的节点
            if (history[i][0] != cars[i][1]) cout << " ";
            else break;
        }

        // 打印每两个站台之间的距离
        cout << " Distances: ";
        for (int j = 1; j < history[i].size(); j++) {
            int u = history[i][j - 1];
            int v = history[i][j];
            cout << roadlength[u][v] << " ";
        }
        cout << endl;
    }

    // 输出总耗时
    int sum = 0;
    for (int i = 0; i < M; i++) {
        sum += car_arrival_time[i];
    }
    cout << sum << endl;

    return 0;
}